题目分析

本题也是大家的老熟人了，但是本题的思维有一些特别，如果能想到关键点，实现逻辑是难不倒大家的。

并查集

并查集是容易想到的，尤其是地图分块、关系分组的问题，基本上都要第一时间想到并查集。虽然使用DFS和BFS也可以求解，但是思路都没有并查集这么直观。

在分析中说的关键点是：一共就两个组，哪些元素应该在同一组，哪些应该在另一组？

加入编号1不喜欢2、3、4、5，那么是否可以得出一个结论，2、3、4、5一定在同一组呢？

因此我们先建立一个关系矩阵，i不喜欢的人一定都在同一个组中。因此将i不喜欢的人相连，然后再判断是否和i相连即可。

所以算法的**时间复杂度为O(n^2)，空间复杂度为O(n)**。

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        for (int[] pair : dislikes) {
            g.get(pair[0] - 1).add(pair[1] - 1);
            g.get(pair[1] - 1).add(pair[0] - 1);
        }
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            List<Integer> cur = g.get(i);
            if (cur.size() > 0) {
                int first = cur.get(0);
                for (int j = 1; j < cur.size(); j++) {
                    uf.union(first, cur.get(j));
                }
                if (uf.isSameRoot(i, first)) {
                    return false;
                }
            }
        }
        return true;
    }
}

class UnionFind {
    int n;
    int[] root;
    
    UnionFind (int n) {
        this.n = n;
        root = IntStream.range(0, n).toArray();
    }
    
    public void union(int x, int y) {
        int rootX = getRoot(x);
        int rootY = getRoot(y);
        if (rootX != rootY) {
            root[rootX] = rootY;
        }
    }
    
    public int getRoot(int x) {
        if (x != root[x]) {
            root[x] = getRoot(root[x]);
        }
        return root[x];
    }
    
    public boolean isSameRoot(int x, int y) {
        return getRoot(x) == getRoot(y);
    }
}

刷题总结

一般来说地图分块和关系分组问题，都是逐渐搜索符合条件的点，并加入到本区域内。本题有一定的思维跳跃性，将和自己关系不好的点都放在同一个组中，这是本题难以想到的，如果想明白这个逻辑，实现也比较简单。